package cn.com.guage.dtm.huawei;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class BinaryTreePreorderTraversal {

    // 递归实现先序遍历
    public List<Integer> preorderTraversalRecursive(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        recursiveHelper(root, result);
        return result;
    }

    private void recursiveHelper(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        result.add(node.val);
        recursiveHelper(node.left, result);
        recursiveHelper(node.right, result);
    }

    // 迭代实现先序遍历
    public List<Integer> preorderTraversalIterative(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return result;
    }


}

public class guage_二叉树先序遍历 {
    public static void main(String[] args) {
        // 构建一个简单的二叉树
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);

        BinaryTreePreorderTraversal solution = new BinaryTreePreorderTraversal();

        // 递归先序遍历
        List<Integer> recursiveResult = solution.preorderTraversalRecursive(root);
        System.out.println("递归先序遍历结果: " + recursiveResult);

        // 迭代先序遍历
        List<Integer> iterativeResult = solution.preorderTraversalIterative(root);
        System.out.println("迭代先序遍历结果: " + iterativeResult);
    }
}
